package 剑指offer;

public class _14剪绳子 {
    public int cuttingRope(int n) {
        // 这里小于4的话，不切分才是最好的，但是由于题目要求是m>1,所以这里直接判断了
        if(n < 2) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;

        int[] products = new int[n+1];

        // 1,2,3 不应该切分的情况
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;

        int max = 0;
        for(int i = 4; i <= n; ++i) {
            max = 0;
            for(int j = 1; j <= i/2; j++) {
                int product = products[j] * products[i-j];
                if(max < product) {
                    max = product;
                }
                products[i] = max;
            }
        }
        return products[n];
    }
}
